---
id: unit5
title: 第五章  关系与函数
---


5.1 关系及关系的性质

设A、B是任意两个集合，AXB的子集R称为从A到B的二元关系，简称为关系。特别地，当A＝B时，称R为A上的关系。如果＜x，y＞ER，可记为xRy，称x与y有关系R；如果＜x，y＞R，则记为xRy，称x与y没有关系R。

［单选、填空、计算］关系的定义域、值域、域。

设R是集合A上的二元关系，

（1）R中所有有序对的第一元素构成的集合称为R的定义域，记为domR，表示为

domR={x|ヨy(\&lt;x,y\&gt;ER)}。

（2）R中所有有序对的第二元素构成的集合称为R的值域，记为ranR，表示为

ranR={y|ヨx(\&lt;x,y\&gt;ER)}。

（3）R的定义域和值域的并集称为R的域，记为fldR，fldR＝domR U ranR。

［单选、计算］关系矩阵。

设给定两个有限集合X＝｛x1，x2，，xm｝，Y＝｛y1，y2，··，yn｝，R为X到Y的一个二元关系，称矩阵MR＝（rij）mxn为对应于R的关系矩阵，其中

1，当＜xi，yj＞ER，

0，当＜xi，yj＞R。

［计算］关系图。

设集合X＝｛x1，x2，，xm｝到Y＝｛y1，y2，＊m，yn｝的二元关系为R，在平面上作出两


·16·

组顶点，其中一组顶点对应X中的元素，另一组顶点对应Y中的元素，两组顶点分别记作

和y1，y2，，yn。如果x；Ry；，则自顶点x；至顶点y；画一条有向边（带方向的

线段），边上的方向由x指向y；；如果xRyy，则x；与y；间没有边相连，由此得到R的

关系图。

［单选、填空、计算、证明］关系的性质。

设R是集合A上的二元关系，

（1）如果对VaEA，必有aRa，则称关系R在A上是自反的。

（2）如果对VaEA，必有aRa，则称关系R在A上是反自反的。

（3）对Va，bEA，若aRb必有bRa，则称关系R在A上是对称的。

（4）对Va，bEA，若aRb且bRa必有a＝b，则称关系R在A上是反对称的。

（5）对Va，b，cEA，若aRb且bRc必有aRc，则称关系R在A上是传递的。

关系的性质还可以通过关系矩阵和关系图给予验证。

（1）若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图上每个顶点都有到自身的有向边。

（2）若关系R是反自反的，当且仅当关系矩阵对角线上的元素皆为0，关系图上每个顶点都没有到自身的有向边。

（3）若关系R是对称的，当且仅当关系矩阵是对称矩阵，且在关系图上，任何两个顶点间若存在有向边，必是成对出现。

（4）若关系R是反对称的，当且仅当关系矩阵中rj＊rj＝0（i≠j），即以主对角线为对称的两个元素不能同时为1，在关系图上两个不同顶点间的有向边，均不会成对出现。

5.2 关系的运算

设R是从X到Y的二元关系，如将R中每一个二元组中的元素顺序互换，所得到的集合称为R的逆关系，简称为R的逆，记作R-1或RC，即R-1＝｛＜y，x＞｜＜x，y)ER}。

［单选、填空、计算］逆关系的性质。

设R、R1、R2都是从A到B的二元关系，则下列各式成立：

(1)(R-1)-1=R。

(2)(R1 U R2)-1=R1-1UR2-1。

(3)(R1nR2)-1=R1-1nR2-1。


第5章关系与函数


(4)(R)-1=(R-1)。

(5)(AxB)-1=BXA。

(6)(R1-R2)-1=R1-1-R2-1。

（7）若R1≤R2，则R1-1CR2-1。

(8)domR-1=ranR。

(9)ranR-1=domR。

［单选、填空、计算］复合关系。

设R为A到B的关系，S为B到C的关系，则R。S称为R和S的复合关系，表示为：R。S= {\&lt;x,y\&gt;|3t(\&lt;x,t\&gt;ERA\&lt;t,y\&gt;ES)}。

设R是集合A上的关系，幂R＂（n＝1,2，···）递归地定义为R1＝R，R&quot;=Rm-1。R。

［单选、填空、计算］关系的闭包。

设R是非空集合A上的二元关系，若关系R＇满足下列条件：

（1）R＇是自反的（对称的或传递的）。

(2)RCR&#39;。

（3）对于A上的任何包含R的自反的（对称的或传递的）关系R&quot;，有R＇CR&quot;。称R＇为R的自反（对称或传递）闭包，记作r（R）（s（R）或t（R））。

设R是非空有穷集合A上的二元关系，则

(1)r(R)=RUIA。

(2)s(R)=RUR-1。

（3）t（R）＝RUR2U···UR＂，其中n是集合A中元素的数目。

5.3 等价关系与序关系

设R为非空集合A上的关系，若R是自反的、对称的和传递的，则称R是A上的等价关系。

设R为等价关系，若＜x，y＞ER，称x等价于y，记作x～y。

给定非空集合A，若有集合S＝｛S1，S2，··，Sm｝，其中S；≤A，S；≠Ø（1≤i

≤m），且S；nS；＝Ø（i≠j），同时有US；＝A，称S是A的划分，每个S；（1≤i≤m）称

为一个分块。

i=1


离散数学

·18·

集合A的一个划分确定A的元素间的一个等价关系，划分中的集合是等价类。

设A是一个非空集合，如果A上的关系R满足自反性、反对称性及传递性，则称R是A上的一个偏序关系，记作&quot;≤&quot;。集合A和A上的偏序关系≤一起称为偏序集，记为（A，≤＞。

设（A，≤＞为偏序集，对Va，bEA，若a＜b且不存在cEA使得a＜c＜b，则称b覆盖a。记COVA ＝ ｛＜a，b＞｜aEAAbEAAb覆盖a｝。

［计算、综合应用］哈斯图的画法。

表示偏序关系的关系图称为哈斯图，表示规则为：

（1）A中每个元素可用顶点表示。

（2）Va，bEA，若a＜b，则将a画在b的下方。

（3）Va，bE A，若b覆盖a，则在a与b之间画一条边。

（4）哈斯图中省略从顶点到自身的边。

［计算、综合应用］最小元、最大元、极小元、极大元。

设＜A，≤＞是一个偏序集，BCA，yEB，

（1）若Vx（xEB→y≤x）成立，则称y为B的最小元。

（2）若Vx（xEB→x≤y）成立，则称y为B的最大元。

（3）若Vx（xEBAx≤y→x＝y）成立，则称y为B的极小元。

（4）若Vx（xEBAy≤x→x＝y）成立，则称y为B的极大元。

设（A，≤＞为一偏序集，对于BCA，如有aEA，且对B中的任意元素x都满足x≤a，则称a为子集B的上界；同样对于B中的任意元素x都满足a≤x，则称a为子集B的下界。

设（A，≤＞是一个偏序集，对于BCA，若a为子集B的任一上界，且对B的所有上界y均有a≤y，则称a为子集B的最小上界（上确界）；同样若b为子集B的任一下界，且对B的所有下界z均有z≤b，则称b为子集B的最大下界（下确界）。

5.4 函数

［单选］设F、G都是X到Y上的函数，它们有相同的定义域和值域，即domF＝domG，ranF＝ranG，且对VxEX都有F（x）＝G（x），称函数F与G是相等的，并记作F＝G.

［单选、计算］单射、满射、双射。

（1）函数f称为一对一的，当且仅当对于f定义域中的所有x和y，f（x）＝f（y）蕴含


第5章关系与函数

·19·

着x＝y。-对一函数也称为单射函数或人射函数。离散数学


（2）给定函数f：X-Y，当且仅当对VyEY，都有x€X使得f（x）＝y，则函数f称为满射的或映上的。

（3）给定函数f：X→Y，函数／既是满射的又是单射的，则称f为一一对应的，也称为双射的。

设f是从X到Y的双射函数，定义函数：Y中的任一元素y，对应于X中满足f（x）＝y的唯一的元素x，称为f的反函数。f的反函数表示为f二。当f（x）＝y时，f-1(y)=x。

设f：X→Y，g：Y→Z，函数f和g的复合f。g（x）＝g（f（x）），具体表示为：fog（x）＝｛＜x，z＞｜（xEX）＾（xEZ）＾3y（yEY＾y＝f（x）Az＝g（y））），复合函数也称为合成函数。

［单选、填空、计算］复合函数的性质。

设f：X→Y，g：Y→Z，fog：X→Z，

（1）若f和g都是满射的，则复合函数f。g也是满射的。

（2）若f和g都是单射的，则复合函数f。g也是单射的。

（3）若f和g都是双射的，则复合函数fog也是双射的。
